Rabin Fingerprint (1981)

Let file $f = 010…1101$ of length $n$ be interpreted as an $n$ bit integer, i.e. between 0 and $2^n$. Construct $h$ randomly: choose random prime number $p$ between 2 and $tn \log(tn)$ for a constant $t$. $$h(f)=f \pmod p$$ $h(f)$ takes $\log(p)$ bits to store

#incomplete

See also: Miller-Rabin randomized primality test (1976, 1980)

Used in Rabin–Karp_algorithm #incomplete

References:

1. M. O. Rabin, ‘Fingerprinting by random polynomials’, Technical report, 1981.
2. https://www.cs.cmu.edu/afs/cs/academic/class/15451-f14/www/lectures/lec6/karp-rabin-09-15-14.pdf
3. https://en.wikipedia.org/wiki/Rabin_fingerprint